#ifndef UTIL_H
#define UTIL_H

#include "StlDep.h"

//获取树的深度
template<typename T>
int Depth(T *root)
{
    if(root==NULL)
        return 0;
    int leftDep=Depth(root->left);
    int rightDep=Depth(root->right);

    return (leftDep>rightDep?leftDep:rightDep)+1;
}

//这个Display函数用来打印树的结构，方便学习AVL、Splay等Tree
//
//如果有这样的树结构:
//             8
//       5           12
//   3      7     10     13
//
//则可以看成下面的样子
//|<-----a---->8
//|<--b->5<----a---->12
//   3      7     10     13
//
//第一层离屏幕左边的距离为a
//第二层离屏幕左边的距离为a/2=b,但是第二层中每一个节点之间的距离是a,这样刚好形成一个交错
//以此类推
//
template <typename T>
void Display(const string& msg, T * root)
{

    //如果一个节点是NULL,则用这个来做占位
    T  Place;
    T *PlaceHolder=&Place; 

    //表示当前层的节点
    vector<T *> curLayer;
    //表示下一层的节点
    vector<T *> nextLayer;

    //取得树的深度
    int treeDepth=Depth<T>(root);

    //输出缓冲区
    char output[treeDepth][240];
    memset(output,' ',treeDepth*240);
    //设置字符串结束符
    for(int i=0; i<treeDepth; ++i)
        output[i][239]=0;

    bool flag=true;
    //初始工作
    curLayer.push_back(root);

    //当前节点用到的宽度
    int curWidth=32;
    //父节点用到的宽度
    int parentWidth=curWidth;
    //记录当前打印的第N层
    int layer=0;
    while(flag)
    {

        //表示当前节点是这一层Layer中首个被打印的节点
        bool first=true;
        //当前被打印节点在output中的位置
        int pos=0;

        //下面对curLayer进行遍历，对curLayer中的节点取得其左右子树保存到
        //nextLayer中
        for(int i=0; i<curLayer.size(); ++i)
        {
            T *tmp=curLayer[i];
            //curLayer中当前节点不为NULl
            if(tmp!=NULL && tmp!=PlaceHolder)
            {
                if(first)
                {
                    first=false;
                    //当前是第一个打印节点，也是当前层的第一个节点
                    if(i==0)
                        pos=curWidth;
                    //当前是第一个打印节点，但不是当前层的第一个节点,这里的currentWidth相当于第一个节
                    //点距离屏幕最左边的偏移，而没有加上currentWidth之前的pos则是该节点在当前层中的相对
                    //偏移位置
                    //
                    //|<------ curWidth ------> |<-------------------------pos节点偏移---------------------->|
                    //|<---离屏幕左边的偏移---> XX <---节点偏移---> XX <---节点偏移---> XX <---节点偏移---> XX
                    else
                        pos=pos+curWidth;
                }

                //下面根据这个偏移在output输出缓冲区中打印相应的值
                int len=sprintf(&output[layer][pos],"%d",tmp->value);
                //这一步消除掉由sprintf打印时加的\0结束字符
                if(len>0)
                    output[layer][pos+len]=' ';
 
                //保存得到下一层的节点数据
                nextLayer.push_back(tmp->left);
                nextLayer.push_back(tmp->right);

            //这种情况需要用PlaceHolder来占一个位子
            }else if(tmp==NULL)
            {
                nextLayer.push_back(PlaceHolder);
                nextLayer.push_back(PlaceHolder);
            }

            //调整下一个节点输出的偏移
            pos+=parentWidth;
        }

        //计算下一层节点与当前节点的偏移
        parentWidth=curWidth;
        curWidth/=2;

        //下面做个检查，如果nextLayer中所有元素都是PlaceHolder，则此nextLayer就不
        //用处理了
        flag=false;
        for(int i=0; i<nextLayer.size(); ++i)
        {
            if(nextLayer[i]!=PlaceHolder && nextLayer[i]!=NULL)
            {
                flag=true;
                //交换nextLayer中的数据到curLayer中
                curLayer.swap(nextLayer);
                nextLayer.clear();
                break;
            }
        }
        ++layer;
    }

    //输出处理完后的内容
    cout<<msg<<endl;
    for(int i=0; i<treeDepth; ++i)
    {
        cout<<&output[i][0]<<endl;
    }
    cout<<endl;
}


#endif
